package com.aaron.leetcode.lc23;

import jdk.nashorn.internal.runtime.linker.LinkerCallSite;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

/**
 * @author liurong
 * @date 2022/1/26 16:09
 * @version:
 */
//方法可行，k个链表，维护一个长为k的list，按顺序放每个链表中未处理的最小的,还有问题，不浪费时间了
public class Solution23_1 {

    int listsNum = 4;

    ListNode[] lists;

    {
        lists = new ListNode[listsNum];
        Random random = new Random();
        for (int index = 0; index < listsNum; index++) {
            List<ListNode> nodes = random.ints(random.ints(1, 1, 10).findFirst().getAsInt(), 0, 100).sorted().mapToObj(ListNode::new).collect(Collectors.toList());
            for (int i = 0; i < nodes.size() - 1; i++) {
                nodes.get(i).next = nodes.get(i + 1);
            }
            lists[index] = nodes.get(0);
        }


    }

    {
        lists = new ListNode[listsNum];
        List<List<Integer>> list = Arrays.asList(
                Arrays.asList(14, 17, 25, 29),
                Arrays.asList(5, 6, 37, 67, 73),
                Arrays.asList(24, 46, 48, 65, 79, 87),
                Arrays.asList(13, 28, 39));
        for (int i = 0; i < list.size(); i++) {
            ListNode node = new ListNode(list.get(i).get(0));
            lists[i] = node;
            for (int j = 1; j < list.get(i).size(); j++) {
                ListNode nextNode = new ListNode(list.get(i).get(j));
                node.next = nextNode;
                node = nextNode;
            }
        }
        System.out.println();

    }

    public ListNode mergeKLists(ListNode[] lists) {
        List<ListNode> nodeMemo = new ArrayList<>();
        for (int i = 0; i < lists.length; i++) {
            nodeMemo.add(lists[i]);
        }
        //记录一个最后节点
        //每个nodelist维护一个待处理node
        int min = -1;
        ListNode start;
        ListNode cur;
        boolean end = false;
        List<Integer> l;
        List<ListNode> cc = nodeMemo.stream().sorted((n1, n2) -> {
            return n1.val - n2.val;
        }).collect(Collectors.toList());
        start = cc.get(0);
        cur = null;
        while (!nodeMemo.isEmpty()) {
            l = new ArrayList<>();
            List<ListNode> collect = nodeMemo.stream().sorted((n1, n2) -> {
                return n1.val - n2.val;
            }).collect(Collectors.toList());
//            int i = 0;
            nodeMemo = new ArrayList<>();
            while (collect.size()>0){

                ListNode minNode =null;
                ListNode back = null;

                if (collect.size() < 1) {
                    return start;
                }
                minNode = collect.remove(0);
                if (cur != null) {
                    cur.next = minNode;
                }
                try {
                    while ( minNode.val<=collect.get(0).val){
                        back = minNode;
                        minNode = minNode.next;
                        if (minNode == null) {
                            break;
                        }
                    }
                } catch (Exception e) {
                    System.out.println();
                }
                if (null != minNode) {
                    nodeMemo.add(minNode);
                }
                back.next = collect.get(0);
                if (collect.size() == 1) {
                    ListNode xx = collect.remove(0);
                    back.next = xx;
                    if (xx.next != null) {
                        nodeMemo.add(xx.next);
                    }
                    cur = xx;
                    continue;
                }
            }
        }
        //
        ListNode nn = start;
        while (null != nn) {
            System.out.println(nn);
            nn = nn.next;
        }


        return null;
    }

    public static void main(String[] args) throws IOException {

        Solution23_1 solution_23 = new Solution23_1();
//        for (ListNode node : solution_23.lists) {
//            while (null != node.next) {
//                System.out.print(node.val+",");
//                node = node.next;
//            }
//            System.out.println();
//        }
        solution_23.mergeKLists(solution_23.lists);

//        BufferedInputStream in = new BufferedInputStream(new FileInputStream(new File("C:\\Users\\JMJ\\Desktop\\test.txt")));
//        byte[] buffer = new byte[1024];
//        int len=0,tmp=0;
//        while ((tmp = in.read(buffer)) != -1) {
//            len = tmp;
//        }
//        in.close();
//        System.out.println(new String(buffer, 0, len));
////        in.read()
////
////        while (in.read()){
////
////        }
//        BufferedReader bufferedReader = new BufferedReader(new FileReader("C:\\Users\\JMJ\\Desktop\\test.txt"));
////        bufferedReader.
//        String line;
//
//        while ((line = bufferedReader.readLine()) != null) {
//            System.out.println(line);
//        }
//
//
//
//        System.out.println();

    }
}


